#lang sicp
(define (left-branch tree)
  (car tree))
(define (right-branch tree)
  (caddr tree))
(define (entry tree)
  (cadr tree))
(define (make-tree left entry right)
  (list left entry right))

;; 2.63

(define (tree->list1 tree)
  (cond ((null? tree) nil)
        (else
         (append (tree->list1 (left-branch tree))
                 (cons (entry tree)
                       (tree->list1 (right-branch tree)))))))


(define (tree->list tree)
  (define (recurse t res)
    (cond ((null? t) res)
          (else
           (let ((r-res (recurse (right-branch t) res)))
             (let ((cur-res (cons (entry t) r-res)))
               (recurse (left-branch t) cur-res))))))
  (recurse tree nil))


(define t1 '(((() 1 ()) 3 (() 5 ())) 7 (() 9 (() 11 ()))))
(define t2 '((() 1 ()) 3 ((() 5 ()) 7 (() 9 (() 11 ())))))
(define t3 '(((() 1 ()) 3 ()) 5 ((() 7 ()) 9 (() 11 ()))))
(define bl (make-tree (make-tree nil 1 nil) 3 (make-tree nil 4 nil)))
(define br (make-tree (make-tree nil 6 nil) 8 (make-tree nil 10 nil)))
(define t4 (make-tree bl 5 br))

;; for n elements of tree
;; tree->list1 : each of elements of tree are involved, which do append (O(n)), thus , approximately o(n2);
;; tree->list2 : each involed also, but each step is o(1), ultimately o(n);


;; 2.64
(define (list->tree elements)
  (define (partical-tree n elements)
    (cond ((= n 0) (cons nil elements))
          (else
           (let ((left-size (quotient n 2)))
             (let ((left-result (partical-tree left-size elements)))
               (let ((left-tree (car left-result))
                     (rest-elements (cdr left-result))
                     (right-size (- n 1 left-size)))
                 (let ((right-result (partical-tree right-size (cdr rest-elements)))
                       (entry (car rest-elements)))
                   (let ((right-tree (car right-result))
                         (rest-elements (cdr right-result)))
                     (cons (make-tree left-tree entry right-tree)
                           rest-elements)))))))))
  (let ((result (partical-tree (length elements) elements)))
    (car result)))

;;I have a precedure i wish, it take a any list as argument and produce a balanced tree;
;;implement detail: a n of list length, use first half the list (also is half n) to make this left tree, and another half to make this entry and this right tree;

;;number of steps required:
;;each of elements of list are involved, each step is o(1), so O(n), strictly, n is all nodes number on the tree, nil node count;


;; 2.65
(define (union-set set1 set2)
  (let ((list1 (tree->list set1))
        (list2 (tree->list set2)))
    (list->tree (union-set-of-ordered-list list1 list2))))

(define (intersection-set set1 set2)
  (let ((list1 (tree->list set1))
        (list2 (tree->list set2)))
    (list->tree (intersection-set-of-ordered-list list1 list2))))

(define (union-set-of-ordered-list list1 list2)
  (cond ((null? list1) list2)
        ((null? list2) list1)
        (else
         (let ((cur1 (car list1))
               (cur2 (car list2)))
           (cond ((< cur1 cur2)
                  (cons cur1 (union-set-of-ordered-list (cdr list1) list2)))
                 ((> cur1 cur2)
                  (cons cur2 (union-set-of-ordered-list list1 (cdr list2))))
                 (else
                  (cons cur1 (union-set-of-ordered-list (cdr list1) (cdr list2)))))))))
(define (intersection-set-of-ordered-list list1 list2)
  (cond ((or (null? list1) (null? list2)) nil)
        (else
         (let ((cur1 (car list1))
               (cur2 (car list2)))
           (cond ((< cur1 cur2)
                  (intersection-set-of-ordered-list (cdr list1) list2))
                 ((> cur1 cur2)
                  (intersection-set-of-ordered-list list1 (cdr list2)))
                 (else
                  (cons cur1 (intersection-set-of-ordered-list (cdr list1) (cdr list2)))))))))

;; O(n) tree to list , union set of ordered list , list to tree;